{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bitwise AND of Numbers Range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rangeBitwiseAnd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数字范围按位与"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数 <code>left</code> 和 <code>right</code> ，表示区间 <code>[left, right]</code> ，返回此区间内所有数字 <strong>按位与</strong> 的结果（包含 <code>left</code> 、<code>right</code> 端点）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>left = 5, right = 7\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>left = 0, right = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>left = 1, right = 2147483647\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= left <= right <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bitwise-and-of-numbers-range](https://leetcode.cn/problems/bitwise-and-of-numbers-range/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bitwise-and-of-numbers-range](https://leetcode.cn/problems/bitwise-and-of-numbers-range/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n7', '0\\n0', '1\\n2147483647']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        cnt = 0\n",
    "        # 找到公共前缀\n",
    "        while left < right:\n",
    "            left = left >> 1\n",
    "            right = right >> 1\n",
    "            cnt += 1\n",
    "        \n",
    "        return left << cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left < right:\n",
    "            left = left >> 1\n",
    "            right = right>>1\n",
    "            shift += 1\n",
    "        return left << shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "\n",
    "        left_num = []\n",
    "        while left != 0:\n",
    "            left_num.append(left%2)\n",
    "            left = int(left/2)\n",
    "            \n",
    "        right_num = []\n",
    "        while right != 0:\n",
    "            right_num.append(right%2)\n",
    "            right = int(right/2)\n",
    "\n",
    "        if len(left_num) != len(right_num):\n",
    "            return 0\n",
    "\n",
    "        if len(left_num) == 0:\n",
    "            return 0\n",
    "        \n",
    "        result = 0\n",
    "        for i in range(len(left_num)-1, -1, -1):\n",
    "            if left_num[i] == right_num[i]:\n",
    "                if left_num[i] == 1:\n",
    "                    result += 2 ** i\n",
    "            else:\n",
    "                break\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
    "        t = 0   \n",
    "        while m < n:\n",
    "            m = m >> 1\n",
    "            n = n >> 1\n",
    "            t += 1\n",
    "        return m << t\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left<right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            shift += 1\n",
    "        return left<<shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left < right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            shift += 1\n",
    "        return right << shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left<right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            shift += 1\n",
    "        return left<<shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, l: int, r: int) -> int:\n",
    "        if l == r: return l\n",
    "        ans = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            c = 2**i\n",
    "            if c > r: continue \n",
    "            if l > r: break\n",
    "            if l&c != 0 and r&c != 0:\n",
    "                ans |= c\n",
    "                l -= c\n",
    "                r -= c\n",
    "            else: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "\n",
    "        shift = 0\n",
    "        while left != right:\n",
    "            shift += 1\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "\n",
    "        return left << shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        ans, i = 0, 31\n",
    "        \n",
    "        while i >= 0 and (left >> i) & 1 == (right >> i) & 1:\n",
    "            ans = (ans << 1) | (left >> i) & 1\n",
    "            i -= 1\n",
    "\n",
    "        while i >= 0:\n",
    "            ans <<= 1\n",
    "            i -= 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left < right:\n",
    "            left = left >> 1\n",
    "            right = right >> 1\n",
    "            shift += 1\n",
    "        return right << shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        time=0\n",
    "        if left==0:\n",
    "            return 0\n",
    "        # elif left==right:\n",
    "        #     return left\n",
    "        while right-left>0:\n",
    "            left = left>>1\n",
    "            right = right>>1\n",
    "            time+=1\n",
    "            if left==0:\n",
    "                return 0\n",
    "        return left*2**(time)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        ans = list(bin(right)[2:])\n",
    "        n = len(ans)\n",
    "        for i in range(1,n+1):\n",
    "            if ans[-i] == '0':\n",
    "                continue\n",
    "            check = int(''.join(ans[:-i]) + '0' + '1' * (i-1), 2)\n",
    "            if check >= left:\n",
    "                ans[-i] = '0'\n",
    "        return int(''.join(ans),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        # 计算最高公共前缀位数\n",
    "        bits = 0\n",
    "        while left != right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            bits += 1\n",
    "\n",
    "        # 将最高公共前缀左移相应位数\n",
    "        return left << bits\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        \"\"\"\n",
    "        遍历可以做，但是肯定不能遍历\n",
    "        问题的本质是求解m和n的最长公共前缀\n",
    "        \"\"\"\n",
    "        cnt = 0\n",
    "        while left != right:\n",
    "            left = left >> 1\n",
    "            right = right >> 1\n",
    "            cnt += 1\n",
    "        return left << cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left < right:\n",
    "            left = left >> 1\n",
    "            right = right >> 1\n",
    "            shift += 1\n",
    "        return left << shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        res = 0 \n",
    "        while left < right:\n",
    "            left = left >> 1\n",
    "            right = right >> 1\n",
    "            res +=1\n",
    "        return left << res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while left < right:\n",
    "            right = right & (right - 1)\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while left < right:\n",
    "            right &= (right - 1)\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left < right:\n",
    "            left = left >> 1\n",
    "            right = right >> 1\n",
    "            shift += 1\n",
    "        \n",
    "        return left << shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
    "        while m < n:\n",
    "            # 抹去最右边的 1\n",
    "            n = n & (n - 1)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        ct = 0\n",
    "        while left<right:\n",
    "            left>>=1\n",
    "            right>>=1\n",
    "            ct+=1\n",
    "        return right<<ct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift=0\n",
    "        while left<right:\n",
    "            left=left>>1\n",
    "            right=right>>1\n",
    "            shift+=1\n",
    "        return left<<shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        step = 0\n",
    "        while left < right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            step += 1\n",
    "        return left << step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        count = 0\n",
    "        while left != right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            count += 1\n",
    "        return left << count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
    "        shift = 0   \n",
    "        # 找到公共前缀\n",
    "        while m < n:\n",
    "            m = m >> 1\n",
    "            n = n >> 1\n",
    "            shift += 1\n",
    "        return m << shift\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
    "        while m < n:\n",
    "            # 抹去最右边的 1\n",
    "            n = n & (n - 1)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while left < right:\n",
    "            right = right & (right-1)\n",
    "        return right \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        count = 0\n",
    "        while left < right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            count += 1\n",
    "        return left << count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left<right:\n",
    "            left = left>>1\n",
    "            right = right>>1\n",
    "            shift += 1\n",
    "        return left<<shift\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        l, r = left, right\n",
    "        sum = 0\n",
    "        while(l < r):\n",
    "            l >>= 1\n",
    "            r >>= 1\n",
    "            sum += 1\n",
    "        \n",
    "        return l << sum\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def Tobit(n):\n",
    "    arr=[]\n",
    "    while n>=2:\n",
    "        arr.append(n&1)\n",
    "        n=n>>1\n",
    "    arr.append(n)\n",
    "    return arr\n",
    "\n",
    "def reverse(arr):\n",
    "    sum=0\n",
    "    for i in range(len(arr)):\n",
    "        sum+=arr[i]<<i\n",
    "    return sum\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        a=Tobit(left)\n",
    "        b=Tobit(right)\n",
    "        flag=1\n",
    "        if len(a)!=len(b):\n",
    "            return 0\n",
    "        for i in range(len(a)-1,-1,-1):\n",
    "            if a[i]!=b[i]:\n",
    "                flag=0\n",
    "                a[i]=b[i]=0\n",
    "            elif flag==0:\n",
    "                a[i]=b[i]=0\n",
    "        return reverse(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
    "        t = 0\n",
    "        while m != n:\n",
    "            m >>= 1\n",
    "            n >>= 1\n",
    "            t += 1\n",
    "        return n << t\n",
    "\n",
    "# 考虑范围[m, n]，如果n比m二进制位数高的话，在累计按位与的过程中，数字的每一个二进制位数必然都出现过0，所以一旦出现位数不同的情况，结果必然为0。\n",
    "\n",
    "# 程序中，m, n在向右移位的过程中，如果m, n相等了，就说明累计按位与的左边肯定等于m, n此时的状态，这时候就可以向左移回来了，相当于右边所有位数都补0，相等的部分照旧。\n",
    "\n",
    "# 如果m, n位数不相等，肯定会移到底，两者都为0时才会相等停止循环，这时候再向左移多少结果都是0。\n",
    "\n",
    "# 作者：typingMonkey\n",
    "# 链接：https://leetcode.cn/problems/bitwise-and-of-numbers-range/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while left < right:\n",
    "            right = right & (right - 1)\n",
    "        return right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while left < right:\n",
    "            right &= (right - 1)\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while left < right:\n",
    "            right -= (right & (-right))\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        # 解法1\n",
    "        # if (left == 0):\n",
    "        #     return 0\n",
    "        # ret = left\n",
    "        # for i in range(left,right+1):\n",
    "        #     ret &= i\n",
    "        # return ret\n",
    "\n",
    "        \n",
    "        ret = 0\n",
    "        while left < right:\n",
    "           left >>= 1\n",
    "           right >>= 1\n",
    "           ret += 1\n",
    "        \n",
    "        return left<<ret\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        # 找left和right的公共前缀\n",
    "        i = 0\n",
    "        while(left != right):\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            i += 1\n",
    "        return left << i\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        m = left\n",
    "        n = right\n",
    "        while m < n:\n",
    "            m = m >> 1\n",
    "            n = n >> 1\n",
    "            shift += 1\n",
    "\n",
    "        return m << shift\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left < right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            shift += 1\n",
    "        return left << shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:  \n",
    "        #只需要找最长公共前缀即可\n",
    "        #证明：假设到公共前缀下标为i，则i+1之后的必定不相同，left=0，right=1\n",
    "        #在left 到 right 过程中必然经过100..(i+1到32位)，则右侧&的结果必然是0\n",
    "        shift = 0\n",
    "        while left != right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            shift += 1\n",
    "        return right << shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        step = 0\n",
    "        while right != left:\n",
    "            right = right >> 1\n",
    "            left = left >> 1\n",
    "            step += 1\n",
    "        return right << step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        ct = 0\n",
    "        while left<right:\n",
    "            left>>=1\n",
    "            right>>=1\n",
    "            ct+=1\n",
    "        return right<<ct\n",
    "        \n",
    "        '''while left<right:\n",
    "            right&=(right-1)\n",
    "        return right\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            st = left >> i & 1\n",
    "            end = right >> i & 1\n",
    "            length = right - left + 1\n",
    "            if st == 1 and end == 1 and length <= 2 ** i:\n",
    "                ans += 2 ** i\n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        i = 0\n",
    "        while left != right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            i += 1\n",
    "        return left << i\n",
    "        # ans = left\n",
    "        # curr = left+1\n",
    "        # while curr <= right:\n",
    "        #     i = 0\n",
    "        #     curr_copy = curr\n",
    "        #     while ans != curr_copy:\n",
    "        #         ans >>= 1\n",
    "        #         curr_copy >>= 1\n",
    "        #         i += 1\n",
    "        #     ans <<= i\n",
    "        #     curr += 1\n",
    "\n",
    "        # return ans\n",
    "            \n",
    "\n",
    "\n",
    "        # ans = 0xffffffff\n",
    "        # for num in range(left, right+1):\n",
    "        #     ans &= num\n",
    "\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        i = 0\n",
    "        while left != right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            i += 1\n",
    "        return left << i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left < right:\n",
    "            left>>= 1\n",
    "            right >>=1\n",
    "            shift += 1\n",
    "        return left<<shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        same_pos = -1\n",
    "        same_length = 0\n",
    "        res = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            r_1 = (right & (1 << i)) >> i\n",
    "            l_1 = (left & (1 << i)) >> i\n",
    "            if r_1 == 1 and l_1 == 1:\n",
    "                if same_pos < 0:\n",
    "                    same_pos = i\n",
    "                same_length += 1\n",
    "            elif r_1 == 1 and l_1 != 1:\n",
    "                break\n",
    "            elif r_1 != 1 and l_1 == 1:\n",
    "                break\n",
    "            else:\n",
    "                if same_pos > 0:\n",
    "                    same_length += 1\n",
    "        \n",
    "        while same_length > 0 and same_pos >= 0:\n",
    "            res += (right & (1 << (same_pos - same_length + 1)))\n",
    "            same_length -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while left < right:\n",
    "            right = right & (right - 1)\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        result = 0\n",
    "        while left != right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            result += 1\n",
    "        return left << result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        ans = 1\n",
    "        while left < right:\n",
    "            right &= (right - 1)\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        shift = 0\n",
    "        while left < right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            shift += 1\n",
    "        return left << shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
    "        shift = 0   \n",
    "        # 找到公共前缀\n",
    "        while m < n:\n",
    "            m = m >> 1\n",
    "            n = n >> 1\n",
    "            shift += 1\n",
    "        return m << shift\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        n = 0\n",
    "        while left < right:\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "            n += 1\n",
    "        return right << n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        # 只要某一位上有一个0，则按位与后就为0\n",
    "        shift = 0\n",
    "        while left < right:\n",
    "            left = left >> 1\n",
    "            right = right >> 1\n",
    "            shift += 1\n",
    "        return right << shift\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while right > left:\n",
    "            right = right & (right - 1)\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def rangeBitwiseAnd(self, left, right):\n",
    "        while left < right:\n",
    "            right = right & (right - 1)\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while left<right:\n",
    "            right&=(right-1)\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "class Solution:\r\n",
    "    \r\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\r\n",
    "        shift = 0   \r\n",
    "        # 找到公共前缀\r\n",
    "        while left < right:\r\n",
    "            left = left >> 1\r\n",
    "            right = right >> 1\r\n",
    "            shift += 1\r\n",
    "        return left << shift\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        while left < right:\n",
    "            right ^= right& - right\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, left: int, right: int) -> int:\n",
    "        if left == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while 2 ** count <= left:\n",
    "            count += 1\n",
    "        count -= 1\n",
    "        if 2 ** (count + 1) > right:\n",
    "            return 2 ** count + self.rangeBitwiseAnd(left- 2**count, right - 2**count)\n",
    "        return 0\n",
    "        t = left\n",
    "        while t:\n",
    "            t >>= 1\n",
    "            count += 1\n",
    "        if 2 ** count + 1 <= right:\n",
    "            return 0\n",
    "        if 2 ** count > left:\n",
    "            return 2 ** (count -1)\n",
    "        return 2 ** count\n",
    "        res = left\n",
    "        for num in range(left + 1, right + 1):\n",
    "            res &= num\n",
    "            if res == 0:\n",
    "                return 0\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
